package algorithm.leetcode.I101to200;

import algorithm.leetcode.ListNode;

/**
 * 注意不需要fake节点
 */

public class Q142 {

    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;

        ListNode fast = head, slow = head;

        // 通过快慢指针先找到环中相遇的点
        boolean hasCycle = false;
        boolean start = true;
        while (fast != null && fast.next != null) {
            if (fast == slow && !start) {
                hasCycle = true;
                break;
            }
            start = false;
            fast = fast.next.next;
            slow = slow.next;
        }

        // 如果有环,快指针从头开始
        if (!hasCycle) fast = null;
        else {
            fast = head;
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
        }
        return fast;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        // ListNode listNode2 = new ListNode(2);
        // ListNode listNode3 = new ListNode(3);
        // ListNode listNode4 = new ListNode(4);
        // listNode1.next = listNode2;
        // listNode2.next = listNode3;
        // listNode3.next = listNode4;
        // listNode4.next = listNode2;

        Q142 tzs = new Q142();
        // tzs.detectCycle(listNode1);
        System.out.println(tzs.detectCycle(listNode1));
    }

}
